Educational Codeforces Round 109 (Div. 2) C Robot Collisions
問題概要
$ n台のロボットが, ある座標$ x_iから, 左もしくは右に速度$ 1で移動する.
壁が座標$ 0と$ mにあり, ロボットは壁にぶつかると向きを変え, そのまま反対方向に移動する.
複数のロボットが整数座標で出会うと消滅する.
各ロボットについて, そのロボットが消滅したかどうか調べ, 消滅したならその時刻を求めよ.
解法
あらかじめロボットを$ x_iの昇順にソートしておく.
パリティに注目する. すると偶奇が等しい座標のロボット同士で衝突するから, パリティごとに分けて考えて良いということがわかる. ここで, 条件を緩くした壁のない場合の問題について考える. そこで, 左に移動するロボットは必ず右に移動するロボットと衝突することを踏まえると, 左に移動するロボットの場合のみ衝突を考えるとしてもよいことがわかる. よって, この部分問題は次のように実装することで解くことができる.
左向きのロボットについて衝突判定を行い, 右向きのロボットについては候補として配列$ vに追加していく. 衝突判定について, $ vが空の場合は何もしない. そうでない場合, 末尾のロボットと必ず衝突するから, 末尾の値を$ vから削除する. 衝突する時刻はロボット間の距離を$ 2で割った値となる. すべてのロボットについてこれらの操作を行った後, $ vに残ったロボットについては何もしない.
では, 壁のある場合について考えてみよう. 実はこの場合も壁のない場合と基本的には同様の方針で解くことができる. 実装において変更点が2つある. まず, 左向きのロボットについて, $ vが空の場合, そのロボットの左にはロボットがいないので, 壁による反射をこのロボットを$ -x_iから出発する右向きのロボットに変更することで扱うことができる. また, すべてのロボットについて操作を行った後, $ vにロボットが残っている場合, 末尾と末尾から$ 2番目の右向きロボットについて, 末尾のロボットの反射をこのロボットを$ 2m - x_iから出発する左向きのロボットに変更することで末尾から$ 2番目のロボットとの衝突として扱い, これを繰り返すという操作を行う.
このようにしてこの問題を$ O(N \log N)で解くことができた.